//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2
//输出：2
//解释：有两种方法可以爬到楼顶。
//1. 1 阶 + 1 阶
//2. 2 阶 
//
// 示例 2： 
//
// 
//输入：n = 3
//输出：3
//解释：有三种方法可以爬到楼顶。
//1. 1 阶 + 1 阶 + 1 阶
//2. 1 阶 + 2 阶
//3. 2 阶 + 1 阶
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 45 
// 
// Related Topics 记忆化搜索 数学 动态规划 
// 👍 2170 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution70 {
    /**
     * 解题思路：动态规划
     * 1.找规律， 发现1个楼梯为1，2个楼梯为2，3个楼梯为3， 4个楼梯为5， 5个楼梯为8， 斐波拉契数列结果
     * 2.dp[n]: 表示第几个楼梯
     * 3.推导公式为 dp[i] = dp[i-1] + dp[i-2];
     * 4.数组初始化： dp[0]=1; dp[1]=1;
     * 5.遍历顺序：遍历顺序， 从第3个元素开始遍历，从前向后遍历
     * 解答成功:
     * 			执行耗时:0 ms,击败了100.00% 的Java用户
     * 			内存消耗:38.2 MB,击败了7.50% 的Java用户
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if(n == 1) return 1;

        int[] dp = new int[n+1];
        dp[0]=1;
        dp[1]=1;

        if(n < 2) return dp[n];

        for(int i=2; i<=n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];


    }
}
//leetcode submit region end(Prohibit modification and deletion)
